from LeetCoder import *



class Solution:

    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        r = 500
        f = [inf] * r
        f[0] = 0
        for j in range(r):
            for i in range(n):
                c, t = cost[i], time[i]
                f[j] = min(f[j], f[max(0, j - t)] + c)
        ans = inf
        for i in range(r):
            if i >= n - i:
                ans = min(ans, f[i])
        return ans


s = Solution()
print(s.paintWalls([42, 8, 28, 35, 21, 13, 21, 35], [2, 1, 1, 1, 2, 1, 1, 2]))
print(s.paintWalls(cost=[1, 2, 3, 2], time=[1, 2, 3, 2]))
print(s.paintWalls(cost=[2, 3, 4, 2], time=[1, 1, 1, 1]))
